package dp;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 368. 最大整除子集
 */
public class P368 {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        Arrays.sort(nums);
        List<Integer> result = new ArrayList<>(nums.length);
        bt(0, nums, new ArrayList<>(), result);
        return result;
    }

    public List<Integer> dp(int[] nums) {
        Arrays.sort(nums);
        int len = nums.length;
        int[] dp = new int[len];
        int[] dpIdx = new int[len];
        dp[0] = 1;
        dpIdx[0] = -1;
        for (int i = 1; i < len; i++) {
            int now = nums[i];
            // 找最大的组
            int maxIdx = -1, maxSize = 1;
            for (int j = i - 1; j >= 0; j--) {
                int num = nums[j];
                if (now % num == 0) {
                    int total = dp[j] + 1;
                    if (total > maxSize) {
                        maxSize = total;
                        maxIdx = j;
                    }
                }
            }
            //
            dp[i] = maxSize;
            dpIdx[i] = maxIdx;
        }
        // 找最大的返回
        int max = 0, idx = -1;
        for (int i = 0; i < len; i++) {
            if (dp[i] > max) {
                max = dp[i];
                idx = i;
            }
        }
        List<Integer> list = new ArrayList<>();
        while (idx >= 0) {
            list.add(0, nums[idx]);
            idx = dpIdx[idx];
        }
        return list;
    }

    private void bt(int begin, int[] nums, List<Integer> savedList, List<Integer> result) {
        if (begin == nums.length) {
            if (savedList.size() > result.size()) {
                result.clear();
                result.addAll(savedList);
            }
        } else {
            for (int i = begin; i < nums.length; i++) {
                int num = nums[i];
                boolean flag = true;
                for (int n : savedList) {
                    if (num % n != 0) {
                        flag = false;
                        continue;
                    }
                }
                if (flag) {
                    // 选择
                    savedList.add(num);
                    bt(i + 1, nums, savedList, result);
                    savedList.remove(savedList.size() - 1);
                }
                bt(i + 1, nums, savedList, result);
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[]{2, 3, 8, 9, 27};
        List<Integer> result = new P368().dp(nums);
        System.out.println(result);
    }
}
